#include "BinaryLinkTree.h"

BinaryLinkTree::BinaryLinkTree()
{
    // root = nullptr;
    root = nullptr;
    
}

BinaryLinkTree::~BinaryLinkTree()
{
    
}

void BinaryLinkTree::Insert(ElementType data)
{
   root = InsertNode(root,data);
}

void BinaryLinkTree::Remove(ElementType element)
{
    root = RemoveNode(root,element);
}

ElementType *BinaryLinkTree::Find(ElementType element)
{
    return FindNode(root,element);
}

ElementType *BinaryLinkTree::FindByIndex(int index)
{
    return FindNodeByIndex(root,index);
}

void BinaryLinkTree::show()
{
    PrevTravel(root);
    std::cout<<std::endl;
    MidTravel(root);
    std::cout<<std::endl;
    PostTravel(root);
    std::cout<<std::endl;
}

void BinaryLinkTree::SetCallbackCompareID(int (*CompareIDPtr)(ElementType, ElementType))
{
     CompareID = CompareIDPtr;
}

void BinaryLinkTree::SetCallbackShowStudent(void (*ShowStudent)(ElementType))
{
     ShowStu = ShowStudent;
}

void BinaryLinkTree::SetCallbackSearchByIndex(int (*SeachID)(ElementType, int))
{
     SearchIDByIndex = SeachID;
}

void BinaryLinkTree::PrevTravel(Node *node)
{
    if(node == nullptr)
        return;
    ShowStu(node->data);
    PrevTravel(node->left);
    PrevTravel(node->right);
}

void BinaryLinkTree::MidTravel(Node *node)
{
    if(node == nullptr)
        return;
    MidTravel(node->left);
    ShowStu(node->data);
    MidTravel(node->right);
}

void BinaryLinkTree::PostTravel(Node *node)
{
    if(node == nullptr)
        return;
    PostTravel(node->left);
    PostTravel(node->right);
    ShowStu(node->data);
}

BLTree::Node* BinaryLinkTree::InsertNode(Node*node, ElementType data)
{
    //终止条件
    if(node == nullptr)
        return new Node(data);
    //
    if(CompareID(node->data ,data) == 0)
        return node;
    //左子树
    if(CompareID(node->data ,data) > 0)
    {
        node->left = InsertNode(node->left,data);
        //失衡
        //左子树重
        if(LeftRightDeviation(node) > 1)
        {   
            // 左左失衡
            if(CompareID(node->left->data ,data) > 0)
            {
               node = RotateRight(node);
            }
            //
            else
            {
                node = RotateLeftRight(node);
            }
        }
    }
    else
    {
        node->right = InsertNode(node->right,data);

        //右子树重
        if(LeftRightDeviation(node) < -1)
        {   
            //右左失衡
            if(CompareID(node->right->data ,data) > 0)
            {
                node = RotateRightLeft(node);
            }
            //右右失衡
            else
            {
                node = RotateLeft(node);
            }
        }
    }
    return node;
}

int BinaryLinkTree::GetNodeHight(Node *node)
{   
    if(node == nullptr)
        return 0;
   int lh = GetNodeHight(node->left);
   int rh = GetNodeHight(node->right);
   return (lh > rh ? lh : rh)+1;
}

int BinaryLinkTree::LeftRightDeviation(Node *node)
{
    return GetNodeHight(node->left) - GetNodeHight(node->right) ;
}

ElementType *BinaryLinkTree::FindNode(Node *node, ElementType data)
{   
    if(node == nullptr)
        return nullptr;
    if(CompareID(node->data ,data) == 0)
        return &node->data;
    else if(CompareID(node->data ,data) > 0)
    {
        return FindNode(node->left,data);
    }
    else
    {
        return FindNode(node->right,data);
    }
}

ElementType *BinaryLinkTree::FindNodeByIndex(Node *node, int index)
{
    if(node == nullptr)                 
        return nullptr;
    if(SearchIDByIndex(node->data,index) == 0)  
        return &node->data;
    else if(SearchIDByIndex(node->data,index) > 0)
        return FindNodeByIndex(node->left,index);
    else                                
        return FindNodeByIndex(node->right,index);
}

BLTree::Node *BinaryLinkTree::RemoveNode(Node *node, ElementType element)
{   
    if(node == nullptr)
    return node;

    if(CompareID(node->data ,element) > 0)
    {
        node->left = RemoveNode(node->left,element);
    }
    else if(CompareID(node->data ,element) < 0)
    {
        node->right = RemoveNode(node->right,element);
    }
    else
    {   
        //只有一个孩子
        if(node->left == nullptr || node->right == nullptr)
        {
            Node *temp = node->left ? node->left : node->right;
            //叶子
            if(temp == nullptr)
            {
                delete node;
                node = nullptr;
            }
            else
            {   
                temp->parent = node->parent;
                delete node;
                node = temp;
            }
        }
        else
        {
            Node *min = GetMinNode(node->right);
            node->data = min->data;
            node->right = RemoveNode(node->right,min->data);
        }
    }

    if(node == nullptr)
        return node;
    //左子树重
    if(LeftRightDeviation(node) > 1)
    {   
        //左子树的左边更重
        if(LeftRightDeviation(node->left) > 0)
        {
            node = RotateRight(node);
        }
        //左右
        else
        {
            node = RotateLeftRight(node);
        }
    }
    else if(LeftRightDeviation (node) < -1)
    {   
        //右左
        if(LeftRightDeviation(node->right) > 0)
        {
            node = RotateRightLeft(node);
        }
        //右右
        else
        {
            node = RotateLeft(node);
        }
    }
    return node;
}

BLTree::Node *BinaryLinkTree::GetMinNode(Node *node)
{   
    Node *min = node;
    while(min->left !=  nullptr)
        min = min->left;
    return min;
}

BLTree::Node *BinaryLinkTree::RotateLeft(Node *node)
{   
    Node * t = node->right;
    node->right = t->left;
    t->left = node;

    t->parent = node->parent;
    node->parent = t;
    return t;
}

BLTree::Node *BinaryLinkTree::RotateRight(Node *node)
{   
    Node *t = node->left;
    node->left = t->right;
    t->right = node;

    t->parent = node->parent;
    node->parent = t;
    return t;
}

BLTree::Node *BinaryLinkTree::RotateLeftRight(Node *node)
{   
    //先把左子树左旋
    node->left = RotateLeft(node->left);
    //右旋
    return RotateRight(node);
}

BLTree::Node *BinaryLinkTree::RotateRightLeft(Node *node)
{   
    node->right = RotateRight(node->right);
    return RotateLeft(node);
}
